In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
King Byteasar has decided to throw two great parties and wants to invite to them every single Byteotian inhabitant. Of course he wants to invite each of them to exactly one of the parties. The king knows from his own vast experience that a person is having a good time when there is an even number of her/his friends at the party. Thus he has asked you to divide the country's inhabitants between two parties in a way that as many people as possible have an even number of friends at their party. A trivial division, i.e. one that leaves one party with no guests invited, is allowed. The acquaintanceship is a symmetric relation, i.e. whenever a person knows the person
, the person
also knows the person
.
Write a programme that:
In the first line of the standard input there is one integer (
) - it is the number of inhabitants of Byteotia. The inhabitants are numbered from
to
. In the following
lines there are the descriptions of subsequent persons' acquaintances. At the beginning of the
'th line there is an integer
(
) - the number of friends of the ith inhabitant. It is followed by
pairwise distinct numbers of the
'th inhabitant's friends. We assume that no inhabitant is her/his own friend. It follows that each acquaintance is written twice: if
and
know each other, then
appears on
's list of friends and
appears on
's.
In the first line of the standard output your programme should write one integer - the number of people who are to come to the first party. In the second line the
numbers of these people should be written. The rest shall come to the second party.
There are many correct divisions in this task - your programme should write any one of them.
For the input data:
5 3 2 3 4 2 1 3 4 2 1 4 5 2 1 3 1 3
the correct result is:
3 1 2 3
In the above example everyone will have even number of friends at the party.
Task author: Wojciech Guzicki.